循环队列 |
您所在的位置：网站首页 › 设某循环队列中有m个元素 且规定 › 循环队列 |
循环队列
|
循环队列--队列的顺序表示和实现
定义队列顺序存储结构，在元素出队时，只是改变指针的位置，不移动元素，可简化操作，节约时间。但这样的话，队列的每个存储空间自始至终只能存储一个队列元素。即使这个队列元素出队后，其他的队列元素也不能占用这个存储空间。这样存储空间浪费较大。因此，考虑使用循环队列。 将顺序队列臆造为一个环状的空间，当队尾元素占据了存储空间的最后一个单元，如再有元素入队，不是申请新的存储空间，而是将新元素插入到存储空间的第一个单元，只要这个单元为空（元素已出队）。
在循环队列中，队尾指针可能小于队头指针。元素入队时，队尾指针加 1 。当队列满时，队尾指针等于队头指针，和队列空时的条件一样。为了区别队满和队空，在循环队列中，少用一个存储单元。 也就是在存储空间为 MAX_QSIZE 的循环队列中，最多只能存放 MAX_QSIZE-1 个元素。这样，队列空的条件仍为队尾指针等于队头指针，队列满的条件改为 (队尾指针+1)对 MAX_QSIZE 求余等于队头指针 。
typedef int Status; /* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef int Boolean; /* Boolean是布尔类型,其值是TRUE或FALSE */
typedef int QElemType; /* 定义队列元素的类型 */
#include /* malloc()等 */
#include /* EOF(=^Z或F6),NULL */
#include /* exit() */
/* 函数结果状态代码 */
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
/* -------------------------- 队列的顺序存储结构 -----------------------------*/
#define MAXQSIZE 5 /* 最大队列长度(对于循环队列，最大队列长度要减1) */
typedef struct
{
QElemType *base; /* 初始化的动态分配存储空间 */
int front; /* 头指针,若队列不空,指向队列头元素 */
int rear; /* 尾指针,若队列不空,指向队列尾元素的下一个位置 */
}SqQueue;
/* ----------------------------------------------------------------------------*/
void visit(QElemType i)
{
printf("%d ", i);
}
/* 循环队列的基本操作(9个) */
/* -------------------- 基本操作的函数原型说明 ---------------------*/
Status InitQueue(SqQueue *Q);
Status DestroyQueue(SqQueue *Q);
Status ClearQueue(SqQueue *Q);
Status QueueEmpty(SqQueue Q);
int QueueLength(SqQueue Q);
Status GetHead(SqQueue Q, QElemType *e);
Status EnQueue(SqQueue *Q, QElemType e);
Status DeQueue(SqQueue *Q, QElemType *e);
Status QueueTraverse(SqQueue Q, void(*vi)(QElemType));
/* --------------------------------- 基本操作的实现 ------------------------------------*/
Status InitQueue(SqQueue *Q)
{ /* 构造一个空队列Q */
(*Q).base = (QElemType *)malloc(MAXQSIZE * sizeof(QElemType));
if (!(*Q).base) /* 存储分配失败 */
exit(OVERFLOW);
(*Q).front = (*Q).rear = 0;
return OK;
}
Status DestroyQueue(SqQueue *Q)
{ /* 销毁队列Q,Q不再存在 */
if ((*Q).base)
free((*Q).base);
(*Q).base = NULL;
(*Q).front = (*Q).rear = 0;
return OK;
}
Status ClearQueue(SqQueue *Q)
{ /* 将Q清为空队列 */
(*Q).front = (*Q).rear = 0;
return OK;
}
Status QueueEmpty(SqQueue Q)
{ /* 若队列Q为空队列,则返回TRUE,否则返回FALSE */
if (Q.front == Q.rear) /* 队列空的标志 */
return TRUE;
else
return FALSE;
}
int QueueLength(SqQueue Q)
{ /* 返回Q的元素个数,即队列的长度 */
return(Q.rear - Q.front + MAXQSIZE) % MAXQSIZE;
}
Status GetHead(SqQueue Q, QElemType *e)
{ /* 若队列不空,则用e返回Q的队头元素,并返回OK,否则返回ERROR */
if (Q.front == Q.rear) /* 队列空 */
return ERROR;
*e = *(Q.base + Q.front);
return OK;
}
Status EnQueue(SqQueue *Q, QElemType e)
{ /* 插入元素e为Q的新的队尾元素 */
if (((*Q).rear + 1) % MAXQSIZE == (*Q).front) /* 队列满 */
return ERROR;
(*Q).base[(*Q).rear] = e;
(*Q).rear = ((*Q).rear + 1) % MAXQSIZE;
return OK;
}
Status DeQueue(SqQueue *Q, QElemType *e)
{ /* 若队列不空,则删除Q的队头元素,用e返回其值,并返回OK;否则返回ERROR */
if ((*Q).front == (*Q).rear) /* 队列空 */
return ERROR;
*e = (*Q).base[(*Q).front];
(*Q).front = ((*Q).front + 1) % MAXQSIZE;
return OK;
}
Status QueueTraverse(SqQueue Q, void(*vi)(QElemType))
{ /* 从队头到队尾依次对队列Q中每个元素调用函数vi().一旦vi失败,则操作失败 */
int i;
i = Q.front;
while (i != Q.rear)
{
vi(*(Q.base + i));
i = (i + 1) % MAXQSIZE;
}
printf("\n");
return OK;
}
/* 检验以上操作的主程序 */
void main()
{
Status j;
int i = 0, l;
QElemType d;
SqQueue Q;
InitQueue(&Q);
printf("初始化队列后，队列空否？%u(1:空 0:否)\n", QueueEmpty(Q));
printf("请输入整型队列元素(不超过%d个),-1为提前结束符: ", MAXQSIZE - 1);
do
{
scanf_s("%d", &d);
if (d == -1)
break;
i++;
EnQueue(&Q, d);
} while (i < MAXQSIZE - 1);
printf("队列长度为: %d\n", QueueLength(Q));
printf("现在队列空否？%u(1:空 0:否)\n", QueueEmpty(Q));
printf("连续%d次由队头删除元素,队尾插入元素:\n", MAXQSIZE);
for (l = 1; l 0)
printf("现在由队头删除%d个元素:\n", l - 2);
while (QueueLength(Q) > 2)
{
DeQueue(&Q, &d);
printf("删除的元素值为%d\n", d);
}
j = GetHead(Q, &d);
if (j)
printf("现在队头元素为: %d\n", d);
ClearQueue(&Q);
printf("清空队列后, 队列空否？%u(1:空 0:否)\n", QueueEmpty(Q));
DestroyQueue(&Q);
}
运行结果：
以上程序所采用的循环队列存储结构，当队列长度大于 MAX_QSIZE - 1 时，无法动态地增加存储空间。为了使循环队列也能动态地增加存储空间，下面程序不固定队列长度，把队列长度也作为结构体的一个成员。 typedef int Status; /* Status是函数的类型,其值是函数结果状态代码，如OK等 */ typedef int Boolean; /* Boolean是布尔类型,其值是TRUE或FALSE */ typedef int QElemType; /* 定义队列元素的类型 */ #include /* malloc()等 */ #include /* EOF(=^Z或F6),NULL */ #include /* exit() */ /* 函数结果状态代码 */ #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 #define OVERFLOW -2 /* -------------------------- 队列的顺序存储结构 -----------------------------*/ #define QUEUE_INIT_SIZE 5 /* 存储空间初始分配量 */ #define QUEUE_INCREMENT 2 /* 存储空间分配增量 */ typedef struct { QElemType *base; /* 初始化的动态分配存储空间 */ int front; /* 头指针,若队列不空,指向队列头元素 */ int rear; /* 尾指针,若队列不空,指向队列尾元素的下一个位置 */ int queuesize; //队列的长度 }SqQueue; /* ----------------------------------------------------------------------------*/ void print(QElemType i) { printf("%d ", i); } /* 循环队列的基本操作(9个) */ /* -------------------- 基本操作的函数原型说明 ---------------------*/ int QueueLength(SqQueue Q); void EnQueue(SqQueue *Q, QElemType e); Status DeQueue(SqQueue *Q, QElemType *e); void QueueTraverse(SqQueue Q, void(*vi)(QElemType)); Status InitQueue(SqQueue *Q); Status DestroyQueue(SqQueue *Q); Status ClearQueue(SqQueue *Q); Status QueueEmpty(SqQueue Q); Status GetHead(SqQueue Q, QElemType *e); /* --------------------------------- 基本操作的实现 ------------------------------------*/ int QueueLength(SqQueue Q) { // 返回Q的元素个数，即队列的长度 return(Q.rear - Q.front + Q.queuesize) % Q.queuesize; } void EnQueue(SqQueue *Q, QElemType e) { // 插入元素e为Q的新的队尾元素 int i; if (((*Q).rear + 1) % (*Q).queuesize == (*Q).front) { // 队列满，增加存储单元 (*Q).base = (QElemType *)realloc((*Q).base, ((*Q).queuesize + QUEUE_INCREMENT) * sizeof(QElemType)); if (!(*Q).base) // 增加单元失败 exit(ERROR); if ((*Q).front > (*Q).rear) // 形成循环 { for (i = (*Q).queuesize - 1; i >= (*Q).front; i--) (*Q).base[i + QUEUE_INCREMENT] = (*Q).base[i]; // 移动高端元素到新的高端 (*Q).front += QUEUE_INCREMENT; // 移动队头指针 } (*Q).queuesize += QUEUE_INCREMENT; // 增加队列长度 } (*Q).base[(*Q).rear] = e; // 将e插入队尾 (*Q).rear = ++(*Q).rear% (*Q).queuesize; // 移动队尾指针 } Status DeQueue(SqQueue *Q, QElemType *e) { // 若队列不空，则删除Q的队头元素，用e返回其值，并返回OK；否则返回ERROR(见图337) if ((*Q).front == (*Q).rear) // 队列空 return ERROR; *e = (*Q).base[(*Q).front]; // 用e返回队头元素 (*Q).front = ++(*Q).front% (*Q).queuesize; // 移动队头指针 return OK; } void QueueTraverse(SqQueue Q, void(*vi)(QElemType)) { // 从队头到队尾依次对队列Q中每个元素调用函数vi() int i = Q.front; // i指向队头 while (i != Q.rear) // 没到队尾 { vi(Q.base[i]); // 调用函数vi() i = ++i % Q.queuesize; // 向后移动i指针 } printf("\n"); } Status InitQueue(SqQueue *Q) { /* 构造一个空队列Q */ (*Q).base = (QElemType *)malloc(QUEUE_INIT_SIZE * sizeof(QElemType)); if (!(*Q).base) /* 存储分配失败 */ exit(OVERFLOW); (*Q).front = (*Q).rear = 0; (*Q).queuesize = QUEUE_INIT_SIZE; return OK; } Status DestroyQueue(SqQueue *Q) { /* 销毁队列Q,Q不再存在 */ if ((*Q).base) free((*Q).base); (*Q).base = NULL; (*Q).front = (*Q).rear = 0; (*Q).queuesize = 0; return OK; } Status ClearQueue(SqQueue *Q) { /* 将Q清为空队列 */ (*Q).front = (*Q).rear = 0; return OK; } Status QueueEmpty(SqQueue Q) { /* 若队列Q为空队列,则返回TRUE,否则返回FALSE */ if (Q.front == Q.rear) /* 队列空的标志 */ return TRUE; else return FALSE; } Status GetHead(SqQueue Q, QElemType *e) { /* 若队列不空,则用e返回Q的队头元素,并返回OK,否则返回ERROR */ if (Q.front == Q.rear) /* 队列空 */ return ERROR; *e = *(Q.base + Q.front); return OK; } /* 检验以上操作的主程序 */ void main() { Status j; int i, n = 6; QElemType d; SqQueue Q; InitQueue(&Q); printf("初始化队列后，队列空否？%u(1:空 0:否)\n", QueueEmpty(Q)); printf("队列长度为%d\n", QueueLength(Q)); printf("请输入%d个整型队列元素:\n", n); for (i = 0; i < n; i++) { scanf("%d", &d); EnQueue(&Q, d); } printf("队列长度为%d\n", QueueLength(Q)); printf("现在队列空否？%u(1:空 0:否)\n", QueueEmpty(Q)); printf("现在队列中的元素为 \n"); QueueTraverse(Q, print); for (i = 1; i |
【本文地址】
今日新闻 |
推荐新闻 |